#include <iostream>
#include <vector>
using namespace std;

int maxArea(vector<int> &height) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(height.size()<2){
        return 0;
    }

    // find the left and right panel
    vector<int> leftIndex;
    vector<int> rightIndex;

    //left
    int heightest = height[0];
    leftIndex.push_back(0);
    for(int i=1; i<height.size(); ++i){
        if(height[i] > heightest){
            heightest = height[i];
            leftIndex.push_back(i);
        }
    }
    // right
    heightest = height[height.size()-1];
    rightIndex.push_back(height.size()-1);
    for(int i=height.size()-2; i>=0; --i){
        if(height[i] > heightest){
            heightest = height[i];
            rightIndex.push_back(i);
        }
    }

    // ok, we use n2 to find max between left and right
    int maxArea = 0;
    for(int i=0; i<leftIndex.size(); ++i){
        for(int j=0; j<rightIndex.size(); ++j){
            if(rightIndex[j] <= leftIndex[i]){
                break;
            }
            int size = min(height[rightIndex[j]], height[leftIndex[i]]) * (rightIndex[j]-leftIndex[i]);
            if(size > maxArea){
                maxArea = size;
            }
        }
    }
    return maxArea;
}

